package leetcode.weekly.week344;

import leetcode.templates.trees.segment.StNode;

//Solution3Test
public class Solution3 {
	public int[] colorTheArray(int n, int[][] queries) {
		StNode root = new StNode(0, n + 100);
		int[] ans = new int[queries.length];
		int[] l = new int[n];
		int[] r = new int[n];
		int[] c = new int[n];
		for (int i = 0; i < n; i++) {
			l[i] = i;
			r[i] = i;
		}
		for (int i = 0; i < queries.length; i++) {
			int[] query = queries[i];
			int idx = query[0], color = query[1];
			if (i > 0) {
				ans[i] = ans[i - 1] - (r[idx] - l[idx]);
			}
//			if()
		}
		return null;
	}

	public class StNode {

		private int LeftRange, Mid, RightRange;
		private StNode leftChild, rightChild;
		private Integer value;

		public StNode(int left, int right) {
			this.LeftRange = left;
			this.RightRange = right;
			this.Mid = ((this.RightRange - this.LeftRange) >> 1) + this.LeftRange;
			this.value = 0;
		}

		private StNode leftNode() {
			if (this.leftChild == null) {
				this.leftChild = new StNode(this.LeftRange, this.Mid);
			}
			return this.leftChild;
		}

		private StNode rightNode() {
			if (this.rightChild == null) {
				this.rightChild = new StNode(this.Mid + 1, this.RightRange);
			}
			return this.rightChild;
		}

		private void addValue(int value) {
			this.value = this.value == null ? value : this.value + value;
		}

		public void add(int left, int right, int add) {
			if (left > right) {
				return;
			}
			if (left == this.LeftRange && right == this.RightRange) {
				this.addValue(add);
			} else {
				pushdown();
				this.leftNode().add(left, Math.min(this.Mid, right), add);
				this.rightNode().add(Math.max(this.Mid + 1, left), right, add);
			}
		}

		public int query(int index) {
			if (this.LeftRange == index && index == this.RightRange) {
				return value;
			}
			pushdown();
			if (index <= this.Mid) {
				return this.leftNode().query(index);
			}
			return this.rightNode().query(index);
		}

		private void pushdown() {
			if (this.value != null) {
				this.leftNode().addValue(this.value);
				this.rightNode().addValue(this.value);
				this.value = null;
			}
		}

	}
}
